package com.company.bs2021;

import java.util.Arrays;

/**
 * 3.单诃搜索(20分）
 *
 * <p>问题描述:
 * <p>给给定一个m x n二维字符网格 board和一个字符串单词word。如果word存在于网格中，
 * 则返回该word 在board中的位置;如果word不存在则返回空。
 * <p>单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水
 * 平相邻或垂直相邻的单元格;同一个单元格内的字母不允许被重复使用。
 *
 * <p>要求:
 * <br>完成题目对应的程序模板(WordSearch）中的方法:int[i][2] findWord(char[m][n] board,String word) ;
 * <br>该方法的入口参数board为给定的m(行) x n(列)二维字符网格，word为给定的单词字符串;
 * <br>最后输出结果为单词word在board的坐标(行,列)序列(坐标值从0开始,);
 * <br>假定word在网格矩阵中最多出现一次。
 *
 * <p>样例:
 * <ul>
 *  <li>样例1
 *      <br>
 *          <table style="border:green solid 1px;">
 *             <tr style="">
 *                 <td align="center" style="border:green solid 1px; width:30px; background-color:blue">A</td>
 *                 <td align="center" style="border:green solid 1px; width:30px;background-color:blue">B</td>
 *                 <td align="center" style="border:green solid 1px; width:30px;background-color:blue">C</td>
 *                 <td align="center" style="border:green solid 1px; width:30px;">E</td>
 *             </tr>
 *             <tr>
 *                   <td align="center" style="border:green solid 1px;">S</td>
 *                   <td align="center" style="border:green solid 1px">F</td>
 *                   <td align="center" style="border:green solid 1px; background-color:blue">C</td>
 *                   <td align="center" style="border:green solid 1px">S</td>
 *              </tr>
 *              <tr>
 *                     <td align="center" style="border:green solid 1px">A</td>
 *                     <td align="center" style="border:green solid 1px; background-color:blue">D</td>
 *                     <td align="center" style="border:green solid 1px; background-color:blue">E</td>
 *                     <td align="center" style="border:green solid 1px">E</td>
 *                </tr>
 *          </table>
 *      <br>输入: board = [['A'，'B','C'，'E'],['S','F'，'C', 'S'],['A'，'D'，'E'，'E']]
 *          <br>word = "ABCCED"
 *      <br>输出:[[0,0]，[0,1],[0,2]，[1,2]，[2,2]，[2,1]]
 *
 *  <li>样例2
 *      <br>输入: board = [['A’，'B'，'C '，'E'],[ 'S'，'F'，'C', 'S']，['A'，'D'，'E'，'E']]
 *      <br>word = "ABCB"
 *      <br>输出: NULL
 * </ul>
 *
 * @author jianf
 * @date 2022年07月07 16:20
 */
public class WordSearch {

    int[][] findWord(char[][] board, String word) {
        int h = board.length;
        int w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        int[][] pos = new int[word.length()][2];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board,visited,i,j,word,0,pos);
                if(flag){
                    return pos;
                }
            }

        }
        return null;
    }

    /**
     * 判断以网格的(i, j) 位置出发，能否搜索到单词word[k..]，其中word[k..] 表示字符串word 从第
     * k 个字符开始的后缀子串。如果能搜索到，则返回true，反之返回false。执行步骤如下：
     * <p>
     * 如果 board[i][j]!=s[k]，当前字符不匹配，直接返回false。
     * <p>
     * 如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回true。
     * <p>
     * 否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串word[k+1..]，
     * 则返回true，否则返回false。
     *
     * @param board   字符网格表
     * @param visited 网格访问记录表
     * @param i       当前网络的行位置
     * @param j       当前网络的列位置
     * @param s       要比对的源串
     * @param k       字符串上位置
     * @return
     */
    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k,int [][] pos) {
        //如果 board[i][j]!=s[k]，当前字符不匹配，直接返回false
        if (board[i][j] != s.charAt(k)) {
            return false;
        }
        // 记录匹配上的位置
        pos[k][0] = i;
        pos[k][1] = j;
        // 如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回true
        if (k == s.length() - 1) {
            return true;
        }
        // 到此处，说明当前位置相等，且不是最后一个串。
        // 标识当前位置已被访问，然后进行 回溯查找
        visited[i][j] = true;
        // 定义相邻数组表
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            // 先判断是否出界了
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                // 再判断新位置是否被访问过
                if (!visited[newi][newj] && check(board, visited, newi, newj, s, k + 1,pos)) {
                    // 此处是剪枝优化，一但找到结果，马上返回
                    return true;
                }
            }
        }
        // 本次回溯完成后，一定要记录撤回，否则更换路径之后再找到此单元时将回跳过
        visited[i][j] = false;
        return result;
    }

    public static void main(String[] args) {
        char[][] board= {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        //String word = "ABCCED";
        String word = "EDFSA";

        WordSearch ws = new WordSearch();
        System.out.println(Arrays.deepToString(ws.findWord(board, word)));

    }
}
